package 牛客;



public class NC36二叉搜索树与双向链表 {
    /**
     * 给我一个二叉搜索树的根节点，我就能将二叉搜索树转换成有序的双向链表
     * left:对应链表的前驱指针
     * right：对应链表的后继指针
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        //终止条件
        if (pRootOfTree == null){
            return null;
        }
        //走到这里说明最少存在一个节点
        //此时分三步走：
        //第一步：将根节点的左子树转换成一个双向链表，交给具有改功能的方法
        TreeNode leftHead = Convert(pRootOfTree.left);//返回左子树的头节点，寻找左子树的尾节点
        TreeNode tailNode = leftHead;
        //遍历头节点查找尾节点
        while (tailNode != null && tailNode.right != null){
            tailNode = tailNode.right;
        }
        //走到这里说明此时已经找到了尾节点，将左子树的尾节点和当前共节点拼接在一起，
        // 但是需要判断尾节点是否为空，尾节点为空，则表明整个左子树为空
        //第二步：
        if (tailNode != null){//如果不为空，则拼接
            tailNode.right = pRootOfTree;
            pRootOfTree.left = tailNode;
        }
        //第三步，将右子树转换成双向链表
        TreeNode rightHead = Convert(pRootOfTree.right);

        //判空
        if (rightHead != null){
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }
        return leftHead == null ? pRootOfTree : leftHead;
    }
}
